#include <vector>
#include <string>

using namespace std;

// 思路： 使用深度优先搜索（DFS）来探索所有可能的路径。
class Solution
{
public:
    bool exist(vector<vector<char>> &board, string word)
    {
        int rows = board.size();
        int cols = board[0].size();
        vector<vector<bool>> visit(rows, vector<bool>(cols, false));

        // 遍历每个格子作为起点进行搜索
        for (int i = 0; i < rows; ++i)
        {
            for (int j = 0; j < cols; ++j)
            {
                if (dfs(board, word, 0, visit, i, j))
                {
                    return true;
                }
            }
        }
        return false;
    }
    // 深度优先搜索函数
    // board: 字母网格
    // word: 目标单词
    // index: 当前匹配的字符索引
    // visit: 访问标记数组
    // row, col: 当前搜索的位置
    // 返回值: 是否找到符合条件的路径
    bool dfs(vector<vector<char>> &board, string &word, int index, vector<vector<bool>> &visit, int row, int col)
    {
        if (index == word.size()) // 找到一个符合条件的路径
            return true;
        int rows = board.size();    // 行数
        int cols = board[0].size(); // 列数
        // row >= rows || row < 0 || col >= cols || col < 0 越界判断
        // board[row][col] != word[index] 字符不匹配
        // visit[row][col] 已经访问过
        // 这些情况都不能继续搜索，返回false
        if (row >= rows || row < 0 || col >= cols || col < 0 || board[row][col] != word[index] || visit[row][col])
        {
            return false;
        }
        // 1. 把当前位置设置为访问过了
        visit[row][col] = true;
        // 2. 继续向四个方向搜索
        bool res = false;
        // 为什么要用res |= 而不是 res = ? 因为需要把四个方向的结果都考虑进去
        res |= dfs(board, word, index + 1, visit, row - 1, col); // 头上
        res |= dfs(board, word, index + 1, visit, row + 1, col); // 头下
        res |= dfs(board, word, index + 1, visit, row, col - 1); // 左边
        res |= dfs(board, word, index + 1, visit, row, col + 1); // 右边
        visit[row][col] = false;
        return res;
    }
};